Find function in C++ STL
Find function in C++ STL
Lower Bound in Cpp STL
Upper Bound in C++ STL
is_permutation() in C++ STL
max_element() and min_element() in C++ STL
count() in C++ STL
binary_search() in C++ STL
fill() in C++ STL
rotate() in C++ STL
accumulate() in C++ STL
rand() in C++
find (InputIterator first, InputIterator last, Type val)
Found at Pos: 1
Found at Pos: 1
Since, the find() function searches for an element linearly in the range, therefore, it can be used with any other container like list, map, set, unordered_set, unordered_map, etc. However, some containers like, map, set, unordered_map, unordered_set provides their own implementation of the find() function which works in O(1) time on average, so, it is highly recommended to use the find() function provided by the specific container.
20
30
30 is at position: 4
Using lower_bound() on arrays
We can use lower_bound() function with arrays also. The idea is to pass address of elements instead of iterators. We can pass the address of first element and address just after the last element.20
30
Using lower_bound() to perform Binary Search
The lower_bound() function is internally implemented using Binary Search. Therefore, to perform Binary Search on a container for searching a key using lower_bound() function, we will have to include the below condition in the program:if(it = end_iterator || (*it) != key)
Key not present
else
Key is present
Present
Time Complexity
The lower_bound() function accepts two iterator for determining the start and end of the sorted range. This function takes O(logN) time, if these iterators are random access iterators.30
40
Index of first greater element of 20 : 4
Count of 20: 3
Element Exists
Using upper_bound() on arrays
We can use upper_bound() function with arrays also. The idea is to pass address of elements instead of iterators. We can pass the address of first element and address just after the last element.30
40
Time Complexity
The upper_bound() function accepts two iterator for determining the start and end of the sorted range. This function takes O(logN) time, if these iterators are random access iterators.bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);
first1, last1: Input iterators to the initial and final positions of the first sequence.
first2 : Input iterator to the initial position of the second sequence.
Note: All of the iterators passed as a parameter to the function are
ForwardIterator, i.e., one can only move forward using these iterators in the container.
Return Value:
true : if all the elements in range [first1, last1]
compare equal to those of the range
starting at first2 in any order.
false : Any element missing or exceeding.
YES
NO
YES
max_element(Iterator1, Iterator2);
or,
min_element(Iterator1, Iterator2);
Iterator1: This is a forward iterator denoting the beginning of the range.
Iterator2: This is a forward iterator denoting the end of the range.
Return Value: It returns an iterator pointing to the maximum or
minimum element in the specified range respectively.
Max Element: 90
Min Element: 5
Max Element: 90
Min Element: 4
Using max_element() and min_element() with user-defined function
We can also use the max_element() and min_element() with a user-defined function to compare values according to a specific criteria. Consider an example that we are given a set of points with X and Y coordinates and we need to find the point with maximum and minimum X accordinate.
// C++ program to illustrate max_element()
// and min_element()
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
// Structure to declare Points
struct Point{
int x;
int y;
Point(int i, int j)
{
x = i;
y = j;
}
};
// User defined comparator function to compare
// according to the X-coordinate only
bool myCmp(Point p1, Point p2)
{
return (p1.x < p2.x);
}
int main()
{
// Declaring vector of Points
vector<Point> v = {{5, 4}, {2, 300}, {90, 10}};
auto it = max_element(v.begin(), v.end(), myCmp);
// Print the point with Max X-coordinate
cout<<"Point with max X-coordinate: "
<<"("<<(*it).x<<", "<<(*it).y<<")"<<endl;
it = min_element(v.begin(), v.end(), myCmp);
// Print the point with min X-coordinate
cout<<"Point with min X-coordinate: "
<<"("<<(*it).x<<", "<<(*it).y<<")"<<endl;
return 0;
}Point with max X-coordinate: (90, 10)
Point with min X-coordinate: (2, 300)
int count(Iterator first, Iterator last, T &val)
first, last: Input iterators to the initial and final positions
of the sequence of elements.
Val : Value to match
Number of times 10 appears : 3
Number of times 10 appears : 3
Time Complexity and Internal Working
The count() function internally performs a linear search between the start and end iterators passed to it as parameters and counts the number of occurrences of the given element.bool binary_search(Iterator1, Iterator2 , Value);
Iterator1: It is the begin iterator of the sorted range.
Iterator2: This iterator points to past-the-end
element of the sorted range.
Value: This is the value to be searched for.
Found
Found
binary_search() with user defined comparator function
We can also use the binary_search() function to search for an element in the sorted range according the a specifc criteria by providing a user defined comparator function.
// C++ program for binary_search() in C++ STL
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Structure for a Point
struct Point
{
int x;
int y;
Point(int i, int j)
{
x = i;
y = j;
}
};
// User-defined comparator function to
// compare values according to X-coordinate
bool myCmp(Point p1, Point p2)
{
return p1.x < p2.x;
}
int main()
{
vector<Point> v = {{10, 5}, {2, 100}, {50, 90}};
// Sorting the above set of points
// according to X-coordinate
sort(v.begin(), v.end(), myCmp);
// Point to be searched
Point p(2, 99);
if(binary_search(v.begin(), v.end(), p, myCmp))
cout<<"Found\n";
else
cout<<"Not Found\n";
return 0;
} Found
Time Complexity and Internal Working
The binary_search() function internally uses the lower_bound() function to perform the search operation. Therefore, it is highly recommended to read the post or watch the tutorial of lower_bound() function first.if(it = end_iterator || (*it) != key)
Key not present
else
Key is present
fill(Iterator begin, Iterator end, value);
5 5 5 5
10 5 5 40
5 5 5 5
5 5 5 5
ggggg
void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);
first, last: Forward Iterators to the initial and final positions of
the sequence to be rotated
middle: Forward Iterator pointing to the element within the range [first, last)
that is moved to the first position in the range.
30 40 50 60 10 20
30 40 50 60 10 20
accumulate(first, last, sum);
first: Iterator pointing to the first element of the range.
last: Iterator pointing to the past-the-end element of the range.
sum: initial value of the sum
60
160
40
6000